
/************************************************************
 *
 * Given a matrix, we start our travel from the cell in the
 * upper-left corner of the matrix. In each step, wen can
 * only move right or down. Our destination is the cell in
 * the lower-right corner of the matrix. How many paths we
 * can go through?
 *
 * We can go through all paths recursively. But, it will be
 * a exponential algorithm. The trick is that we can fill
 * each cell in the matrix with a number which indicate how
 * many paths can we go through from this cell to the
 * lower-right corner of the matrix. Suppose this matrix is
 * a[m][n], then we first fill two cells, a[m-1][n-2] and
 * a[m-2][n-1], with number 1 which indicate that there is
 * only one path we can go through from the two cells to the
 * lower-right corner respectively. Then, we fill those
 * cells adjacent to these two cells. The rule is that a[i][j]
 * is equal to a[i+1][j] plus a[i][j+1]. Then, we fill those
 * cells adjacent to these cells which have been filled yet.
 * Once all cells in the matrix have been filled, we output
 * the number in the cell in the upper-left corner of the
 * matrix. It's the answer we need.
 *
 * In addition, if the matrix is too big, the answer should
 * be a very long sequence of digits. Consequently, any data
 * type in c++ programming language can not hold the answer.
 * So, we do arthematic concerning string of characters.
 *
 * Date: 5/29/2008
 ***********************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

#define ZERO   (48)
#define m      (48)
#define n      (34)

char *sum( char *s1, char *s2 )
{
    char *t, *r;
    int carry, s, left, right, i, j, k;

    t = (char *)malloc(sizeof(char)*128);
    i = strlen(s1)-1;
    j = strlen(s2)-1;
    k = 0;
    carry = 0;
    while ( i>=0 || j>=0 ){

	left = i>=0 ? (s1[i--]-ZERO) : 0;
	right = j>=0 ? (s2[j--]-ZERO) : 0;
	s = left + right + carry;
	if ( s >= 10 ){
	    t[k++] = s - 10 + ZERO;
	    carry = 1;
	}
	else{
	    t[k++] = s + ZERO;
	    carry = 0;
	}

    }

    if ( carry ) t[k++] = carry + ZERO;
    t[k] = '\0';

    r = (char *)malloc( strlen(t) + 1);
    for ( i = strlen(t)-1, j = 0; i>=0 ; i--, j++ ) r[j] = t[i];
    r[j] = '\0';
    free(t);

    return r;
}

char *makenum( char * s )
{
    char *r;

    r = (char *)malloc(strlen(s)+1);
    strcpy( r, s );
	return r;
}

int main()
{
    char *a[m][n];
    int i, j;

    for ( i = 0; i <= m-1; i++ )
		a[i][n-1] = makenum( "1" );

    for ( j = 0; j <= n-2; j++ )
		a[m-1][j] = makenum( "1" );

    for ( i = m-2; i >= 0; i-- )
	for( j = n-2; j >= 0; j-- )
	    a[i][j] = sum( a[i+1][j], a[i][j+1] );

	printf("%s\n", a[0][0]);

    for ( i = 0; i < m; i++ )
	for ( j = 0; j < n; j++ )
	    free( a[i][j] );
	
	return 0;
}

